For each possible subarray we compute the sum and store the maximum

brute_force(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	for i = 0 to n
		sum = 0
		for j = i to n
			sum += a[j]
			if sum > max
				max = sum
	return max
Copy

Kadane's algorithm is based on two properties of the subarray with maximum sum:

1. sum of values in any prefix of the optimal subarray is positive. By contradiction, remove a negative prefix to get a subarray with a larger sum
2. the value that precede the first value of the optimal subarray is negative. By contradiction, include this positive value to get a subarray with a larger sum

To solve the problem we use Kadane's algorithm:

kadane_algorithm(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	sum = 0

	for i = 0 to n
		if sum > 0 // property 1)
			sum += arr[i]
		else // property 2)
			sum = arr[i]

		max = Math.max(sum, max)

	return max
Copy

• for each element we scan the array searching for the next number, if we do not find it we return ,
• sort the array then find the missing one,

We use the gauss sum to find the missing number:

• compute the sum of the elements of the array, actualSum
• compute the sum of the first elements: sum =
• return sum - acualSum

Traverse every array element and find the highest bars on the left and right sides.
Take the smaller of two heights.
The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.

The point is to think locally, not globally.
We compute the left and right leaders.

An element of an array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Left leaders are analogous.

Given the array of heights, we use two arrays to store the right and left leaders:

Now, how many units of water we can find on top of the cell ?
The minimum height between the left and right leader of the current position minus , the height of the current position:

Two Pointer Technique, more on this later.
The idea is taken from the Precomputation solution, where we only use two variables to store the currently "meaningful" leaders.

We take two pointers, left and right and we initialize left to 0 and right to the last index n-1.
We also create two variables, left_max and right_max, they represent the maximum left/right height seen so far.

Since left is the first left_max is 0, same for right_max.
This is intuitive: left_max of left = 0 falls outside the array, its height is 0, the same goes for right_max when right = n-1.

Now we iterate, as long as left < right.
We have to decide which pointer we have to shift: we shift the pointer that has smaller height value:

• if heights[left] < heights[right] we shift left
• we shift right otherwise

Now, if we have that heights[left] > left_max we can't store any water over the position pointed by left, it would fall as left_max is not high enough to contain any water over left

Otherwise we compute the amount of water stored in left, as always with left_max - heights[left]. Then we finally shift left by 1.
The reasoning with the right pointer is the same.

The following pseudo-code solves the problem

max_water(heights[]) 
	n = heights.length()
	result = 0
	left = 0
	right = n-1

	left_max = 0 // max height seen by "left" so far
	right_max = 0 // max height seen by "right" so far

	while left < right 
		if heights[left] < heights[right] // shift "left"
			if heights[left] > left_max 
				left_max = heigths[left] // cant store water
			else 
				result += left_max - heights[left]
			left += 1
		else // shift right
			if heights[right] > right_max 
				right_max = heights[right] // cant store water
			else 
				result += right_max - heights[right]
			right -= 1

	return result
Copy

An efficient algorithm that searches for a given key within a sorted array of items.
Binary search repeatedly divides the search range in half until the target element is found or the search range becomes empty, resulting in a time complexity of

Binary search is a technique that falls under the umbrella of the divide-and-conquer paradigm, that tackles a complex problem by breaking it down into smaller, more manageable subproblems of the same type:

• divide: the initial problem instance is partitioned into smaller subinstances of the same problem
• solve: these subinstances are then solved recursively. If a subinstance reaches a certain manageable size, a straightforward approach is employed to solve it directly
• combine: the solutions obtained from the subinstances are combined to obtain the final solution for the original, larger instance of the problem

Considering the binary search, we have:

• divide: the array is divided into two roughly equal halves, centering around the middle element of the array
• solve: compare the middle element of the array with the searched key. If the middle element is a match, the search stop successfully. If not, we recursively search for the key only in one of the two halves that may contain the key, based on whether the desired key is greater or lesser than the middle element
• combine: there is nothing to combine

It is also important to observe that when there are multiple occurrences of the searched key, the function returns the position of the first encountered occurrence, not necessarily the first occurrence in the vector.
However, it is often very useful to report the position of the first (or last) occurrence of the searched key.

We can obtain this behavior with the following pseudo-implementation.

binary_search(a[], target) 
	n = a.length()
	low = 0
	high = n - 1
	answer = -1

	while low < high
		// (low + high)/2 might overflow if (high+low) is very big
		middle = low + (high - low) / 2

		if a[middle] == target
			answer = middle
			high = middle
		else if a[middle] < target
			low = middle
		else 
			high = middle

	return answer
Copy

In this implementation, when a match is found, we do not immediately return its position. Instead, we update the answer variable and set high to the position of this occurrence.
This way, we continue the search in the first half of the array, seeking additional occurrences of the key.
If there are more matches, answer will be further updated with smaller positions.

We can use the binary search philosophy to solve the problem.
We compute the middle of the array.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a leader, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.

peak_elements(a[])
	n = a.length()
	low = 0
	high = n - 1

	while low < high
		mid = low + (high - low) / 2

		if a[mid] < a[mid + 1]
			low = mid + 1
		else 
			high = mid 

	return low 
Copy

This solution works because a leader is guaranteed to be found (as a last resource, in the first or last element of the array).
The beauty of this solution is that it naturally covers all the strange cases.
It would be tempting to write something like

if a[mid] > a[mid+1] && a[mid] > a[mid-1]
	return mid
Copy

but that requires to cover many edge cases (array of size 1, 2, if mid is , if mid is , ...)

Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.
Such traversals are classified by the order in which the nodes are visited.

Traversing a tree involves iterating over all nodes in some manner.
Because from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes are stored implicitly in the call stack.

Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue.

A simple solution is to traverse the tree and do following for every traversed node :

1. Find maximum sum from-leaf-to-root in left subtree of
2. Find maximum sum from-leaf-to-root in right subtree of . 
3. Add the above two calculated values and and compare the sum with the maximum value obtained so far and update the maximum value. 
4. Return the maximum value.

Max Sum leaf-to-root path in a Binary Tree:
Given a Binary Tree, find the maximum sum path from a leaf to root.
For example, in the following tree, there are three leaf to root paths:

• 8 -> -2 -> 10
• -4 -> -2 -> 10
• 7 -> 10.

The sums of these three paths are 16, 4 and 17 respectively.
The maximum of them is 17 and the path for maximum is 7 -> 10.

					              10  
				                 /  \  
				               -2    7  
				              /  \       
				             8   -4
Copy

Solution:

1. First find the leaf node that is on the maximum sum path.
2. Once we have the target leaf node, we can print the maximum sum path by traversing the tree.

Here we provide a Java pseudo-implementation of the problem:

maxValue = 0
targetLeaf = null

maxLeafRootSum(root)
	targetLeaf = findTargetLeaf(root, 0)
	print(maxValue)

// set targetLeaf to the leaf with maximum sum path to root
findTargetLeaf(node, currMaxValue) 
	if root == null
		return 

	// hold the sum of nodes on path from root to this node
	currMaxValue += node.value

	// leaf and the path to this has maximum sum: set targetLeaf
	if node.isLeaf 
		if currMaxValue > maxValue
			maxValue = currMaxValue
			targetLeaf = node

	// this is not a leaf node: recur down to find targetLeaf
	findTargetLeaf(node.left, currMaxValue)
	findTargetLeaf(node.right, currMaxValue)
Copy

So, the trivial solution of Maximum Path Sum works as follows:

• For every node we compute:
  • the maximum path sum from to a leaf,
  • the maximum path sum from to a leaf,
  • we take the maximum between the two
  • we sum the value of X
  • if the sum is greater than the current maximum we update the current maximum

For every node we call twice maxLeafRootSum, which costs O(n), hence the total cost is O(n^2)

We can find the maximum sum using single traversal of binary tree.
The idea is to maintain two values in recursive calls

1. Maximum root-to-leaf path sum for the subtrees rooted under current node. 
2. The maximum path sum between leaves (desired output).

For every visited node , we find the maximum root-to-leaf sum in left and right subtrees of . We add the two values with , and compare the sum with maximum path sum found so far.

As before, here a pseudo-code implementation:

maxValue = 0

// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) root-to-leaf path sum, which is returned.
maxPathSum(root)
	if root == null
		return 0

	left = maxPathSum(root.left)
	right = maxPathSum(root.right)
	
	maxValue = Math.max(maxValue, left + right + root.value)

	return left + right + root.value
Copy

In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:

• take a node
• compute the max sum path from to a leaf and the max sum path from to a leaf .
• the sum path from to (passing by ) is greater than the one previously stored? then we update the max

The result is maxValue when the program terminates.

The naive approach is obvious and takes O(n^2), we simply scan the array and we return when we find two numbers that adds up to X.

existsPairSum(a[], x)
	n = a.length()
	for i = 0 to n
		for j = i+1 to n
			if a[i] + a[j] == x
				return true
			if a[i] + a[j] > x
				break // a is sorted, need a new "i"
	return false
Copy

Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.
It employs using two pointer, typically one from the start of the array going left-to-right and one from the end of the array going right-to-left, until they meet.
We already seen a sneak peak of this in Trapping Rain Water.

We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers.

If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum.
We keep moving the pointers until we get the sum as X.

existsPairSum(a[], x)
	n = a.length()
	left = 0
	right = n-1

	while left < right
		if a[left] + a[right] == x
			return true
		if a[left] + a[right] < x
			left += 1 // smaller than target, we need to increase
		else
			right -= 1 // bigger than target, we need to decrease

	return false
Copy

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

Binary search trees allow binary search for fast lookup, addition, and removal of data items.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.

The complexity analysis of BST shows that, on average, the insert, delete and search takes for n nodes.
In the worst case, they degrade to that of a singly linked list:

We store the position of the frogs in a BST, frogBST.
When a mosquito lands on a position we check which frog will eat it by simply doing a frogBST.predecessor(b) query on the tree.
It is possible that some mosquito cannot be eaten right away, the uneaten mosquito will be stored in their own BST (mosquitoBST), using their landing position as keys.

Sort the frogs by their position and force no overlaps with their reach (position + tongue length).

The algorithm behaves as follows:

• insert the frogs in a BST frogBST using their position as key
• for each mosquito m in mosquitoes
  - find the predecessor f of m in frogBST, if f.position + f.tongue >= m.position
  - f eats the mosquito m and its tongue grows by the size of m
  - maybe f now can eat other mosquitoes that could not be eaten before, inspect mosquitoBST to see if there is a mosquito that f can eat, and in case repeat.
  - inspect: find the successor m' of f.position in mosquitoBST and see if f.position + f.tongue >= m'.position
  - f now may overlap or fully contain other frogs
  - For every successor of f in frogBST:
  - if it overlaps with f remove the overlap by updating their positions
  - position of the successor = f.position + f.tongue + 1
  - if it is fully contained by f then delete this frog as it will never eat
  - else, insert m in mosquitoBST and continue
  
  TODO
  Time Complexity:
• Each predecessor query on the frog tree can be answered in time.
• Each successor query of the mosquito tree can be answered in time.
• Forcing no overlaps: we can "move/shift" frogs at most for every mosquito that is eaten, then

The simplest approach is to consider each of the windows independently.
Within each window we compute its maximum by scanning the window through all its elements, which takes time.
We then have that this brute force approach takes time.

The problem in this approach is that when we compute the maximum of the current window we disregard all the previous computations, done on windows that are partially overlapping to the current one.

To solve more efficiently the problem we need a data structure that handle the next window while capitalizing on the progress made in processing the preceding window.

We consider the two following observations:

1. We can represent the elements within a window with a multiset of size . In this representation the result for the window is essentially the largest element contained within this multiset.
2. When we transition from a window to the next, only two elements change: the first element of the first window exits from the scene and the last one enters (the window slides of one position to the right). Hence, we can derive the multiset of the new window from the multiset of the previous window by adding one element and removing another one.

We then require a data structure capable of performing three crucial operations on a (multi)set:

• inserting a new element
• deleting an arbitrary element
• retrieving the maximum element within the multiset

A Balanced Binary Search Tree (BBST) supports any of these operations in where is the number of elements in the multiset (and it is optimal in the comparison model.)
This way we can solve the problem in time.

In rust we use BTreeSet that offers efficiently the operations insert, remove, and last (find max).
The only hiccup is that it do not store repeated elements, hence we store elements as pair with their index in the array.

A heap is a tree-based data structure that satisfies the heap property:

• max-heap: for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C.
• min-heap: the key of P is less than or equal to the key of C

The main operations are:

• insertion:
  • insert the new element at the bottom of the heap (next available position)
  • perform "heapify up", an operation to restore the heap property by swapping the element with its parent until the heap property is satisfied again
• remove max/min:
  • remove the root element (which is the min or the max of the heap)
  • replace the root with the last element in the heap
  • perform "heapify down", an operation to restore the heap property by swapping the element with one of its children until the heap property is satisfied again
• peek:
  • returning the maximum (or the minimum) without removing takes constant time since it is stored in the root node.

TODO
The BST solution can do more than what is strictly necessary, e.g. what is the second largest element in the window?
The fact that we can do much more than what is requested, it’s an important signal to think that a faster solution could exist.

The better solution uses a deque a double-ended queue, which supports constant time insertion, removal and access at the frond and back of the queue.
There are many ways to implement a deque, the simplest one (but not the fastest) is a bidirectional list.

The algorithm starts with an empty deque and with the window that covers the positions in the range .
That is, the window starts before the beginning of a. Then we start sliding the window one position at a time and remove/insert elements from .
The element in front of the deque will be the element to report.

More precisely, we repeat times the following steps:

• move the window one position to the right
• remove from the head of the elements that are no longer in the window
• insert the new element from the tail of and remove all the elements above it until we find a larger element
• report the head of as the maximum of the current window

Note: the deque stores indices, not actual elements.

// q = [a1, ..., ak]
//      back     front
slidingWindowMaximum(a[]) 
	n = a.length()
	Deque q
	maxs[n-k+1]

	for i = 0 to k 
		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()
			
		q.pushBack(i)

	maxs.push(a[q.front()]);

	for i = k to n 
		// remove elements that dont belongs in the window
		while !q.isEmpty() && q.front() + k <= i
			q.popFront()

		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()

		q.pushBack(i)
		maxs.push(a[q.front()])

	return maxs;
Copy

The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in computational geometry efficiently.
The sweep line algorithm can be used to solve problems on a line or on a plane.

The sweep and line algorithm use an imaginary vertical line sweeping over the x-axis.
As it progresses, we maintain a running solution to the problem at hand.
The solution is updated when the vertical line reaches a certain key points where some event happen. The type of the event tells us how to update the solution.

Let's apply the sweep and line algorithm to the problem above.
We let the sweep line from left to right and stop at the beginning or at the end of every interval.
These are the important points at which an event occurs: interval start or end.
We also maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value reached by the counter so far.

For each point we first add to the counter the number of intervals that begin at that point, and then we subtract the number of intervals that end at that point.
The figure below shows the points touched by the sweep line and the values of the counter:

Observation: The sweep line only touches points on the x-axis where an event occurs.
This is important because the number of considered points, and thus the time complexity, is proportional to the number of intervals, and not to the size of the x-axis.

The following is the intuitive solution.
It has two nested loops, one that iterates right-left times and the inner one that iterates times, where is the number of ranges.
The complexity then is time.

isCovered(ranges, left, right) 
	for i = left to right 
		covered = false // i is not covered until proven otherwise
		for range in ranges 
			if i >= range.start && i <= range.end 
				covered = true // i is covered by the current interval
				break;
			
		// if i is not covered then we return false
		if covered == false 
			return false
	
	// each i in [left, right] is covered by at least one range
	return true;
Copy

To solve the problem more efficiently we use sweep line and a map.
The complexity is linear in the maximum between the number of ranges and right

isCovered(ranges, left, right)
	// map: point i -> number of open ranges in i
	HashMap openRangesAt; 
	for range in ranges 
		openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
		// range.end+1 as the ranges are inclusive!
		openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) - 1)

	openRangesNow = 0
	for i = 0 to left 
		openRangesNow += openRangesNow.getOrDefault(i, 0)

	for point=left to right 
		openRangesNow += openRangesNow.getOrDefault(point, 0)
		if openRangesNow == 0
			return false

	return true
Copy

We use the sliding window approach: the implementation is self-explanatory

longestKGoodSegment(array, k)
	n = array.length()
	if k == 0 || n == 0
		return (-1,-1)
	if k == 1
		return (0,0)

	wSize = 1 // current window size
	left, right = 0 // left and right delimiter of the window
	pointer = 1 // always points to the element just outside the window

	maxWSize = 1 // store the maximum size of the window so far
	leftResult, rightResult = 0 // delimiter of the maximum window

	HashSet distincts // store distinct elements in the window
	distincts.insert(array[0]) // the windows starts with the first element

	while pointer != n // proceed until the pointer is outside the array
		// the element just outside the window is to be included
		if Math.abs(array[right], array[pointer]) == 1
			distincts.insert(array[pointer]);
			right ++ 1 // stretch the window
			wSize ++ 1 // the size of the window grows
			pointer ++ 1 // shift the pointer to be outside of the window
			
			if wSize > maxWSize // the new size is the maximum?
				maxWSize = wSize
				leftResult = left
				rightResult = right 

				if distincts.size() == k // the window contains k distinct?
					return (leftResult, rightResult)
		else 
			left = pointer // shift the window: the start becomes pointer
			right = left // the window is made of one element
			w_size = 1 
			pointer = right+1 // points to the element outside the window
			distincts.clear() // reset the distinct elements in the window

	return (-1,-1)
Copy

The obvious brute force approach: from each element we compute every possible subarray starting in that element, check if sum is a multiple of k and store the maximum length so far.

Prefix sums, also known as cumulative sums or cumulative frequencies, offer an elegant and efficient way to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.

The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.

An example of prefix sum array is shown in the picture:

Where it is clear that

The solution is based on the following mathematical property:
Observation: any two prefix sums that are not next to each other with the same mod k, or a prefix sum with mod k = 0 that is not the first number will yield a valid subarray.

checkSubarraySum(array, k)
	n = array.length()
	
	prefixSumArray[] // prefix sum array
	pS = 0
	for i = 0 to n 
		pS += array[i]
		prefixSumArray[i] = pS

	// map: modulo -> index i st prefixSumArray[i] % k = modulo
	HashMap modsToIndices
	for (i, prefixSum) in prefixSumArray.enumerate() 
		modulo = prefixSum % k

		if modulo == 0 && i != 0 // if modulo is 0 and not the first ok
			return true

		// first time we see this modulo
		if modsToIndices.contains(modulo) == false
			modsToIndices.insert(modulo, i)
		else 
			// this modulo has been seen
			previousIndex = modsToIndices.get(modulo);
			if previousIndex < i - 1
				return true

	return false
Copy

Observation:
We really do not need a full prefix sum array, it is enough to compute sum as we go and use it also as the mod result (we make sum = sum%k and use it as key, sums in modulo works). This is true because we never use the prefix sum of an element before the predecessor, so we can store only the sum up until now.

The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that maintains the prefix sums of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries, both in logarithmic time.

Consider the following problem: we have an array A[1..n] of integers and we would like to support the following operations:

• sum(i) returns the sum of the elements in A[1...i]
• add(i,v) adds the value v to the entry A[i]

We have two trivial solutions:

• Store A as it is. This way, sum(i) is solved by scanning the array in time, and add(i,v) is solved in
• Store the prefix sums of A. This way sum(i) is solved in and add(i,v) is solved modifying all the entries from i to n in time.

The sum/add query time trade-offs of these solutions are unsatisfactory

The Fenwick Tree provides better tradeoffs for this problem.
The Fenwick tree efficiently handles these queries in while using linear space.
In fact the Fenwick tree is an implicit data structure, which means it requires only additional space to the space needed to store the input data, in our case the array A

In our description, we will gradually introduce this data structure by constructing it level by level.

We use the following 1-indexed array in our example:

We start with a simpler version of the problem: we focus on solving sum queries only for positions that are powers of 2, positions 1, 2, 4, 8 in A.
The solution of this simplified version, shown in the picture, will be the first level of the Fenwick Tree

We notice that:

• there is a fictitious root node named 0 (the array is 1-indexed, the root is a dummy as it is an out-of-bound node)
• over every node there is the corresponding index in A
• the value of every node is the prefix sum up to that index
• under every node we have a range of integers: those are the positions covered by that node

With this solution we have that:

• sum(i) query: straightforward, we simply access the node i, provided that i is a power of 2
• add(i,v) query: we need to add v to all the nodes that covers ranges that include the position i, for example if we want to do add(3,10) we need to add 10 to the nodes 4 (as it has range and ) and 8 (as it has range and ).
  • general rule add(i,v): find the smallest power of 2 grater than i, let's call it j, and we add v to the nodes j, j*2, j*(2^2), ... (j is the index in the original array, stored over every node in the picture above)

We observe that sum takes constant time and add takes time.
This is very good, can we extend this solution to support sum queries on more positions?

Observation: currently we are not supporting queries for positions within the ranges between consecutive powers of 2.
Look at the image above: positions that falls in the range (subarray) [5, 7], which falls between the indices () and (), are not supported.
In fact we can't make the query sum(5).
Enabling queries for this subarray is a smaller instance of our original problem.

We can apply the same strategy by adding a new level to our tree.
The children of a node stores the partial sums starting from the next element.
The emphasis is in starting.

If the subarray is A[l..r], the new level will support the sum(i) query for any i such that i-l+1 is a power of 2.

Lemma: our two-level tree can now handle sum(i) queries for positions that are the sum of two powers of 2.
Proof:

• Consider a position i expressed as , where .
• We can decompose the range into two subranges:
• Both of these two subranges are covered by nodes in our tree
  - the range is covered by the node at the first level
  - the range is covered by the node i at the second level
  Example: intuition on how to compute sum(5)
• the range is divided in two subranges
  • , covered by the node 4
  • , covered by the node 5
• the result, which is 16, is obtained by summing the values of the nodes
  • search the node 4 in the tree: it is at the first level as it is a power of 2
  • take its value, which is 9
  • search the node 5
    • it is not a power of two but a sum of power of 2, hence it is at the second level
    • the biggest power of 2 smaller than 5 is 4, hence the node 5 is a children of the node 4
    • take its value, which is 7
  • 9 + 7 = 16

Which are the position still not supported? The positions that are neither a power of 2 or the sum of two powers of 2.
In our example, we can't compute sum(7) as 7 is either of those.
To support this we add a new level to our tree, so we can support positions that are sum of three powers of 2

Example: intuition on how to compute sum(7)

• the position can be expressed with , with , where:
• in fact we have that
• the range can be divided in three subranges:
• and we have that
  • the first subrange is covered by the node 4, which has value = 9
  • the second subrange is covered by the node 6, which has value = 4
  • the third subrange is covered by the node 7, which has value = 2
• the biggest power of 2 smaller than 7 is 4, hence all the useful nodes will be in the subtree rooted in the node 4
  • 4 is a power of 2, first level
  • 6 is the sum of two power of 2, second level
  • 7 is the sum of three power of 2, third level
• 9 + 4 + 5 = 15, which is sum(7)

And we are done, this is the Fenwick tree of the array A.

We can make some observations:

1. While we have represented our solution as a tree, it can also be represented as an array of size n+1, as shown in the figure above
2. We no longer require the original array A because any of its entries A[i] can be simply obtained by doing sum(i) - sum(i-1). This is why the Fenwick tree is an implicit data structure
3. Let be , which is the length of the binary representation of any position in the range . Since any position can be expressed as the sum of at most powers of , the tree has no more than levels. In fact, the number of levels is either or , depending on the value of

Now, let’s delve into the details of how to solve our sum and add queries on a Fenwick tree.

The following is a minimal implementation.
While we’ve transitioned to 0-based indexing for queries, internally, we still use the 1-based indexing to maintain consistency with the examples above.

#[derive(Debug)]
pub struct FenwickTree {
    tree: Vec<i64>,
}
impl FenwickTree {
    pub fn with_len(n: usize) -> Self {
        Self {
            tree: vec![0; n + 1],
        }
    }
    pub fn len(&self) -> usize {
        self.tree.len() - 1
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn add(&mut self, i: usize, delta: i64) {
        let mut i = i + 1; 
        assert!(i < self.tree.len());

        while i < self.tree.len() {
            self.tree[i] += delta;
            i = Self::next_sibling(i);
        }
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn sum(&self, i: usize) -> i64 {
        let mut i = i + 1;  

        assert!(i < self.tree.len());
        let mut sum = 0;
        while i != 0 {
            sum += self.tree[i];
            i = Self::parent(i);
        }
        sum
    }
    pub fn range_sum(&self, l: usize, r: usize) -> i64 {
        self.sum(r) - if l == 0 { 0 } else { self.sum(l - 1) }
    }
    fn isolate_trailing_one(i: usize) -> usize {
        if i == 0 {
            0
        } else {
            1 << i.trailing_zeros()
        }
    }
    fn parent(i: usize) -> usize {
        i - Self::isolate_trailing_one(i)
    }
    fn next_sibling(i: usize) -> usize {
        i + Self::isolate_trailing_one(i)
    }
}
Copy

We are given an array A[1,n] initially set to 0.
We want to support two operations:

• access(i) returns the sum A[1..i]
• range_update(l, r, v), updates the entries in A[l,r] adding to them v

The following Fenwick solution solve the problem

1. from A we build the Fenwick Tree of length n (mind that A is initialized with all zeros)
2. the operation access(i) is a wrapper of the operation sum(i) we have seen before
3. the operation range_update(l,r,v) exploit the operation add(i, v) of the implementation of the Fenwick Tree:
   1. first we check that l is <= than r, aka that the interval of entries to update is well formed
   2. then we check that r <= n, aka that the interval of entries to update is actually in the array
   3. we perform add(l,v): this trigger the addition of the value v to each node whose range include the position l in the Fenwick Tree
   4. we perform add(r, -v): this trigger the subtraction of the value v to each node whose range include the position r in the Fenwick Tree
   5. we have added and subtracted the same same quantity v in the Fenwick tree, this means that prefix sum are coherent and the elements in [l,r] are increased by v

#[derive(Debug)]
struct UpdateArray {
    ft: FenwickTree,
}
impl UpdateArray {
    pub fn with_len(n: usize) -> Self {
        Self {
            ft: FenwickTree::with_len(n),
        }
    }
    pub fn len(&self) -> usize {
        self.ft.len()
    }
    pub fn access(&self, i: usize) -> i64 {
        self.ft.sum(i)
    }
    pub fn range_update(&mut self, l: usize, r: usize, v: i64) {
        assert!(l <= r);
        assert!(r < self.ft.len());

        self.ft.add(l, v);
        if r + 1 < self.ft.len() {
            self.ft.add(r + 1, -v);
        }
    }
}
Copy

We use a sweep line & Fenwick tree approach.

We build an array events where every entry is [l_i, r_i, i], and then we sort events by start of the respective range, l_i.

Then we build the Fenwick tree with size , we scan each event and add in each position in the fenwick tree.

Now we scan the events again.
When we process the event we observe that the segments already processed are only the ones that starts before the current one, as they are sorted by their starting points.

To find the solution of this problem for the current segment (aka the number of segments contained in the current one) we need to know the number of the segments that starts after the current one that also end before the current one, before .
This is computed with a query sum(r_i) on the Fenwick Tree.

After computing the solution for the current segment we subtract to position , to remove the contribution of the right endpoint of the current segment in the next queries.
This is why the segments that starts before the current one but overlaps with it are not counted
The following snippet implement the solution above, using the Fenwick tree previously defined.

fn fenwick_nested_segments(input_segments: &[(i32, i32)]) -> Vec<(i64, usize)> {
	let n = input_segments.len();
	// (start, end, index_in_input)
	let mut events: Vec<(i32, i32, usize)> = Vec::with_capacity(n);
	for (i, &(l, r)) in input_segments.iter().enumerate() {
		events.push((l, r, i));
	}
	// sort by starting endpoint
	events.sort_by(|a, b| a.0.cmp(&b.0));
	let mut tree = FenwickTree::with_len(input_segments.len()*2 + 1);
	for i in 0..n {
		tree.add(events[i].1 as usize, 1);
	}
	let mut sol: Vec<(i64, usize)> = Vec::with_capacity(n);
	for i in 0..n {
		sol.push((tree.sum(events[i].1 as usize) - 1, events[i].2));
		tree.add(events[i].1 as usize, -1);
	}
	// restore so that the solution are paired with the input ordering
	sol.sort_by(|a, b| a.1.cmp(&b.1));
	
	sol
}
Copy

A Segment Tree is a data structure that stores information about array intervals as a tree.
This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array.

The key point here is range queries, not only range sums!
We can find the sum of consecutive array elementsA[l..r] or find the minimum element in a segment in time.
Between answering such queries we can modifying the elements by replacing one element of the array, or even changing the elements of a whole subsegment (e.g., assigning all elements a[l..r] to any value, or adding a value to all element in the subsegment)

Segment trees can be generalized to larger dimensions. For instance, with 2-dimensional Segment trees you can answer sum or minimum queries over some subrectangle of a given matrix in time.

We consider the simplest form of Segment Trees.
We want to answer sum queries efficiently.
The formal definition of our task is the following: given an array , the Segment Tree must be able to perform the following operations in time

1. find the sum of elements between the indices and :
2. change values of elements in the array:

Observation: even our simple form of Segment Tree is an improvement over the simpler approaches:

• a naive implementation that uses just the array can update element in but requires to compute each sum query
• a precomputed prefix sums can compute the sum queries in but updating an array element requires changes to the prefix sums

Let's now solve nested segments with a Segment Tree and Sweep Line

Given the input array segments we compute the maximum endpoint between the segments, and call it n.
Then we create a segment tree, based on an array of length , initialized with all zeroes.
At this point we create the array axis, which stores triples where:

• the first element of the triple is a segment endpoint
• the second element is the index of the endpoint's segment in segments
• the third element is a boolean isStart, which is set to true if the endpoint is the start of its segment, otherwise the end.

We sort axis by the first element, the segments endpoints.
Finally we "sweep" over axis.

• for `i = 0 to axis.length()
  • if axis[i].isStart == false, aka if the current endpoint is the end of its segment
    • the number of nested segments in the segment where axis[i].endpoint, that we call res, is the range sum on the range [segments[axis[i].index, axis[i].endpoint
    • we push the tuple (axis[i].index, res) in the array of results
    • we increase by one the start of the segment indexed with axis[i].index in segments
  • sort results by the indexes and return it

Why it works?


In words:
Consider the segments .

When we find the end of a segment , namely we do the range sum of to get the number of segments contained in the segment .
Then we increase by the segment in the segment tree.

This works because we increase by one the start when its segment has been closed.
The range sum on will count only segments that starts after and have already been closed (otherwise they would be in the tree).

Alternatively said:

• find the end of the segment , .
• do the range sum
  • all the segments that starts after and have already been closed have caused the increment by one of
    • starts after and already been closed, fully contained in
• the segment has been closed, increase by one in the tree.

The Mo’s Algorithm is a powerful and efficient technique for solving a wide variety of range query problems.
It becomes particularly useful for kind of queries where the use of a Segment Tree or similar data structures are not feasible.
This typically occurs when the query is non-associative, meaning that the result of a query on a range cannot be derived by combining the answers of the subranges that cover the original range.

Mo’s algorithm typically achieves a time complexity of , where represents the size of the dataset, and is the number of queries.